문제설명

XX 게임의 유저들이 보스 몬스터를 사냥하려고 팀을 만들었습니다. 그리고 팀에 속한 캐릭터에 아이템을 사용해 공격력을 높이려 합니다.

이 게임의 아이템은 캐릭터의 공격력은 높이고 체력을 낮춥니다. 그래서 아이템을 적절히 사용해 팀의 공격력을 최대한 끌어올리려 합니다. 캐릭터별로 아이템을 사용할지 말지는 자유지만, 아이템을 사용한 캐릭터는 체력이 반드시 100 이상 남아야 합니다. 또, 한 캐릭터에 아이템 하나씩만 사용할 수 있으며, 사용한 아이템은 사라집니다.

예를 들어 캐릭터의 체력이 [200, 120, 150]이고 아이템의 효과는 다음과 같습니다.

높여줄 공격치 낮추는 체력
30 100
500 30
100 400

이때 팀의 공격력을 최대로 올리려면 첫 번째 캐릭터에 첫 번째 아이템을, 세 번째 캐릭터에 두 번째 아이템을 사용하면 됩니다.

캐릭터들의 체력을 담은 배열 healths와 아이템별 효과를 담은 이차원 배열 items가 solution 함수의 매개변수로 주어질 때, 팀의 공격력을 최고로 끌어올리려면 어떤 아이템을 사용해야 하는지 return 하도록 solution 함수를 완성해주세요.

제한 조건

  • healths의 길이는 1 이상 10,000 이하입니다.
  • healths의 원소(캐릭터의 체력)는 1 이상 1,000,000 이하인 자연수입니다.
  • items의 길이는 1 이상 5,000 이하입니다.

  • items에는 아이템이 [올려줄 공격력, 낮출 체력]이 번호 순서대로 들어있습니다.

    • 아이템 번호는 1번 부터 시작합니다.
    • items[i]에는 i + 1번 아이템이 [올려줄 공격력, 낮출 체력]이 들어있습니다.
    • 아이템이 올리는 공격력은 1 이상 500,000 이하인 자연수입니다.
    • 아이템이 내리는 체력은 1 이상 500,000 이하인 자연수입니다.
  • 아이템 번호는 오름차순으로 정렬해 return 해주세요.
  • 올려주는 공격력이 같은 아이템은 없습니다.
  • 아이템을 사용하는 방법이 여러 가지라면, 그러한 방법 중 아무거나 하나를 return 해주세요. 단, 아이템 번호는 오름차순으로 정렬되어 있어야 합니다.

입출력 예

healths items return
[200,120,150] [[30,100],[500,30],[100,400]] [1,2]
[300,200,500] [[1000, 600], [400, 500], [300, 100]] [3]

입출력 예 #1 문제의 예시와 같습니다.

입출력 예 #2

첫 번째, 두 번째 아이템을 사용하면 캐릭터의 체력이 100 미만이 됩니다. 따라서 세 번째 아이템만 사용할 수 있습니다.

나의 풀이

첫번째 풀이

소스

def solution(healths, items):
    answer = []

    healths.sort()

    items = [(item[0], item[1], idx + 1) for idx, item in enumerate(items)]
    items = sorted(items, key=lambda x: x[0], reverse=True)

    for health in healths:
        maxBuffIdx = -1
        for item in items:
            buff, debuff, idx = item
            if health - debuff >= 100:
                maxBuffIdx = idx
                items.remove(item)
                break

        if maxBuffIdx != -1:
            answer.append(maxBuffIdx)

    return sorted(answer)

설명

우선, 이 문제에 대해서는 가장 낮은 체력에 가능한 공격력이 가장 높은 무기를 들려주면 된다라는 생각으로 풀어보았다.

그래서 맨 처음에 낮은 체력 순으로 healths를 sort하고, 공격력 순으로 items를 sort하였다.

그러고 난 뒤에, 2중 for문을 돌면서

주어진 조건인, health - debuff >= 100을 만족하는 index를 답으로 추가하고 item list에서 제거하도록 하였다.

결과

정확성: 90.9
효율성: 4.5
합계: 95.5 / 100.0

2중 for문처럼 보이지만, remove가 O(n)이므로 O(health * item^2)이 되어버린다.

그래서 아마 효율성에서 탈락이지 않을까 싶다…

리뷰

보통 게임 아이템처럼 무언가 최고의 선택을 해야 하는 경우는 우선순위큐(힙) 혹은 그리디로 푸는 경우가 많다. 그 중에서도 최고의 선택을 바로 할 수 없는 경우에는 우선순위 큐를 이용하는게 좋다.

이럴 경우에는 어디에 우선순위 큐를 써야할지 고민을 해야하는데, 가장 좋은 방법은 가장 반복이 자주 일어나는 곳에 사용하는 것.

답 확인

소스

from heapq import heapify, heappush, heappop
from collections import deque


def solution(healths, items):
    answer = []
    healths.sort()
    items = deque(sorted([(item[1], item[0], idx + 1)
                          for idx, item in enumerate(items)]))

    heap_items = []

    # 우선 health for문으로 시작
    for health in healths:
        if health <= 100:
            continue

        # 현재 체력에서 장착 가능한 item들을 구한다. - heap에 넣어 자동소팅되게 (어차피 가장 작은 체력 순으로 sort되어있기 때문에 다음번 health에서는 heap에 있는 item을 모두 장착 할 수 있다.)
        while items:
            debuff, buff, idx = items[0]
            if health - debuff < 100:  # 가장 작게 체력을 낮춰주는 debuff가 안되면 그 다음번것도 안될 것이니 그냥 break
                break

            items.popleft()  # heap에 넣어질 것은 pop
            heappush(heap_items, (-buff, idx))

        # 고를 수 있는 item중에서 가장 높은 공격력을 주는 item 선택
        if heap_items:
            _, idx = heappop(heap_items)
            answer.append(idx)

    return sorted(answer)

설명

이 문제에서 효율성을 따지려면 heap을 사용하여야 되는데, 어떻게 heap을 적용시킬지가 KeyPoint이지 않나 싶다.

답을 참조해보면 우선 healths, items 모두 체력, debuff를 오름차순으로 sort한 후에, healths를 순회하면서 

1. 현재 health에서 착용 가능한 아이템들을 buff를 key(max_heap을 위해 음수화)로 heap에 삽입

2. 착용가능한 item들이 -buff를 키로 자동정렬 되어있는 heap이 비어있지 않으면 pop, idx 정답으로 추가

와 같다.

추가로, pop(0)을 하지않기 위해서 deque를 사용하였다.

이 문제는 이해가 계속 안갔던 문제라 나중에 두고두고 풀어봐야 겠다.